#include <iostream>
using namespace std;

struct Node{
    char data;
    Node *lChild, *rChild;
};

struct BinTree{
    Node *root;
};

void Create(BinTree& T, char x, Node *left, Node *right)
{
    Node *NewNode = new Node;
    NewNode->data = x;
    NewNode->lChild = left;
    NewNode->rChild = right;

    T.root = NewNode;
}

//排序二叉树
void Create(BinTree &T, int x)
{
    Node *NewNode, *p;
    NewNode = new Node;
    NewNode->data = x;
    NewNode->lChild = NULL;
    NewNode->rChild = NULL;

    int flag = 0;

    if(IsEmpty(T))
    {
        T.root = NewNode;
    }
    else
    {
        p = T.root;
        while(!flag)
        {
            if(x < p->data)
            {
                //进入左子树
                if(p->lChild == NULL)
                {
                    p->lChild = NewNode;
                    flag = 1;
                }
                else
                {
                    p = p->lChild;
                }
            }
            else
            {
                //右子树
                if(NULL == p->rChild)
                {
                    p->rChild = NewNode;
                    flag = 1;
                }
                else
                {
                    p = p->rChild;
                }
            }
        }
    }
}

void PreOrder(Node *p)
{
    if(NULL != p)
    {
        cout<<p->data;
        PreOrder(p->lChild);
        PreOrder(p->rChild);
    }
}

void InOrder(Node *p)
{
    if(NULL != p)
    {
        InOrder(p->lChild);
        cout<<p->data;
        InOrder(p->rChild);
    }
}

void PosOrder(Node *p)
{
    if(NULL != p)
    {
        PosOrder(p->lChild);
        PosOrder(p->rChild);
        cout<<p->data;
    }
}
int main()
{
    BinTree K, E, B, C, A;
    Create(K,'K',NULL,NULL);
    Create(E,'E',NULL,K.root);
    Create(B,'B',NULL,E.root);
    Create(C,'C',NULL,NULL);
    Create(A,'A',B.root,C.root);

    cout<<"前序遍历 ：";PreOrder(A.root);
    cout<<"\n中序遍历 ：";InOrder(A.root);
    cout<<"\n后序遍历 ：";PosOrder(A.root);
    
    return 0;
}